package com.test.daily.leetcode.y2022.m05.day0522.v07;

import java.util.HashMap;
import java.util.Map;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/5/22 下午 07:49
 * @version: 1.0
 */
public class Solution {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int maxChoosableInteger = 20, desiredTotal = 152;
        System.out.println(new Solution().canIWin(maxChoosableInteger, desiredTotal));
        long end = System.currentTimeMillis();
        System.out.println("last:" + (end - start));
    }

    public Map<Integer, Boolean> map = new HashMap<>();

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1 + maxChoosableInteger) * (maxChoosableInteger) / 2 < desiredTotal) {
            return false;
        }
        return process(maxChoosableInteger, 0, desiredTotal, 0);
    }

    public boolean process(int maxChoosableInteger, int usedNumber, int desiredTotal, int curTotal) {
        System.out.println(new Integer(usedNumber).byteValue());

        if (!map.containsKey(usedNumber)) {
            boolean ans = false;
            for (int i = 0; i < maxChoosableInteger; i++) {
                if (((usedNumber >> i) & 1) == 0) {
                    if (curTotal + i + 1 >= desiredTotal) {
                        ans = true;
                        break;
                    }
                    //                    usedNumbers | (1 << i)
                    if (!process(maxChoosableInteger, usedNumber | (1 << i), desiredTotal, curTotal + i + 1)) {
                        ans = true;
                        break;
                    }
                }
            }
            map.put(usedNumber, ans);
        }
        return map.get(usedNumber);
    }
}
